#pragma once
#include <ctime>
#include <vector>
#include <string>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <map>
#include <queue>
#include <limits>
#include <iostream>

class Edge {
public:
    int id;
    int u, v;
    time_t t, w;
    std::string to_str() const;
    bool operator== (const Edge& rhs) {
        return id == rhs.id;
    }
};

template <typename T1, typename T2>
struct pair_hash {
    std::size_t operator () (const std::pair<T1, T2>& p) const {
        auto h1 = std::hash<T1>{}(p.first);
        auto h2 = std::hash<T2>{}(p.second);
        return h1 ^ (h2 << 1);
    }
};

struct EdgeOrderByOutTime {
    bool operator()(const Edge& a, const Edge& b) const {
        if (a.t != b.t) return a.t < b.t;
        return a.id < b.id;
    }
};

struct EdgeOrderByInTime {
    bool operator()(const Edge& a, const Edge& b) const {
        if (a.t + a.w != b.t + b.w) return a.t + a.w < b.t + b.w;
        return a.id < b.id;
    }
};

class OSE {
public:
    int n, m, x;
    int source;
    time_t start = 0, end = 0;
    std::unordered_set<int> vertices;
    std::set<Edge, EdgeOrderByOutTime> edges;
    std::unordered_map<int, int> f;
    std::unordered_map<int, std::map<time_t, int>> L;
    std::unordered_map<std::pair<int, time_t>, Edge, pair_hash<int, time_t>> pe;
    std::unordered_map<std::pair<int, time_t>, std::pair<int, time_t>, pair_hash<int, time_t>> ps;
    void caculate(int x, time_t ta, time_t to);
    void add_edges(std::vector<Edge> new_edges);
    void delete_edges(std::vector<Edge> old_edges);
};

struct tuple_hash {
    template <typename T>
    std::size_t operator ()(const T& t) const {
        // 将元组的每个元素的哈希值组合起来
        std::size_t seed = 0;
        std::hash<typename std::tuple_element<0, T>::type> hash1;
        std::hash<typename std::tuple_element<1, T>::type> hash2;
        std::hash<typename std::tuple_element<2, T>::type> hash3;

        seed ^= hash1(std::get<0>(t)) + 0x9e3779b9 + (seed << 6) + (seed >> 2);
        seed ^= hash2(std::get<1>(t)) + 0x9e3779b9 + (seed << 6) + (seed >> 2);
        seed ^= hash3(std::get<2>(t)) + 0x9e3779b9 + (seed << 6) + (seed >> 2);

        return seed;
    }
};

class TRGEdge {
public:
    int id;
    std::tuple<int, time_t, int> u;
    std::tuple<int, time_t, int> v;
    time_t w;
    std::string to_str() const;
};

struct Compare {
    bool operator()(const std::tuple<int, time_t, int, int, int>& a, const std::tuple<int, time_t, int, int, int>& b) const {
        // 按第一位升序比较
        if (std::get<0>(a) != std::get<0>(b)) {
            return std::get<0>(a) > std::get<0>(b); // 升序，所以返回 a > b 时放入优先队列
        }

        // 按第二位降序比较
        if (std::get<1>(a) != std::get<1>(b)) {
            return std::get<1>(a) > std::get<1>(b); // 降序，所以返回 a < b 时放入优先队列
        }

        // 按第三位升序比较
        if (std::get<2>(a) != std::get<2>(b)) {
            return std::get<2>(a) < std::get<2>(b); // 升序
        }

        // 按第四位升序比较
        if (std::get<3>(a) != std::get<3>(b)) {
            return std::get<3>(a) > std::get<3>(b); // 升序
        }

        // 按第五位升序比较
        return std::get<4>(a) > std::get<4>(b); // 升序
    }
};

class TRG {
public:
    int source;
    time_t start, end;
    int m0 = 0, m1 = 0;
    std::unordered_map<int, TRGEdge> edges; // 正数id是正常边，负数id是0边
    std::unordered_map<std::tuple<int, time_t, int>, std::unordered_set<int>, tuple_hash> out;
    std::unordered_map<std::tuple<int, time_t, int>, std::unordered_set<int>, tuple_hash> in;
    std::unordered_map<std::tuple<int, time_t, int>, int, tuple_hash> f;
    std::unordered_map<int, int> ans;
    std::unordered_map<std::tuple<int, time_t, int>, int, tuple_hash> pe;
    std::unordered_map<std::tuple<int, time_t, int>, std::unordered_set<std::tuple<int, time_t, int>, tuple_hash>, tuple_hash> c;
    std::priority_queue<std::tuple<int, time_t, int, int, int>, std::vector<std::tuple<int, time_t, int, int, int>>, Compare> pq;
    std::unordered_map<std::tuple<int, time_t, int>, int, tuple_hash> check;
    std::unordered_map<std::tuple<int, time_t, int>, int, tuple_hash> check_back;
    void caculate(int source, time_t ta, time_t to);
    void tadd_edges(std::vector<TRGEdge> new_edges);
    void tdelete_edges(std::vector<TRGEdge> old_edges);
    void real_add_edges(std::vector<Edge> new_edges);
    void real_delete_edges(std::vector<Edge> old_edges);
    std::unordered_map<int, std::set<time_t>> in_times;
    std::unordered_map<int, std::set<time_t>> out_times;
    std::unordered_map<std::tuple<int, time_t, int>, int, tuple_hash> check2;
    std::unordered_set<std::tuple<int, time_t, int>, tuple_hash> red;
    std::unordered_map<std::tuple<int, time_t, int>, int, tuple_hash> cnt;
};

class ADJ {
public:
    int source;
    time_t start = 0, end = 0;
    int n, m;
    std::unordered_set<int> vertices;
    std::unordered_map<int, Edge> edges;
    std::unordered_map<int, std::set<Edge, EdgeOrderByOutTime>> out;
    std::unordered_map<int, std::set<Edge, EdgeOrderByInTime>> in;
    std::unordered_map<int, int> f;
    std::unordered_map<int, std::map<time_t, int>> L;
    std::unordered_map<std::pair<int, time_t>, int, pair_hash<int, time_t>> dis;
    std::priority_queue<std::tuple<int, time_t, int, int, time_t, int>, std::vector<std::tuple<int, time_t, int, int, time_t, int>>, std::greater<std::tuple<int, time_t, int, int, time_t, int>>> pq;
    std::unordered_map<std::pair<int, time_t>, std::pair<int, time_t>, pair_hash<int, time_t>> ps;
    std::unordered_map<std::pair<int, time_t>, Edge, pair_hash<int, time_t>> pe;
    std::unordered_map<std::pair<int, time_t>, std::unordered_set<std::pair<int, time_t>, pair_hash<int, time_t>>, pair_hash<int, time_t>> c;
    ADJ(std::string filename);
    OSE to_OSE();
    TRG to_TRG();
    void caculate(int x, time_t ta, time_t to);
    void add_edges(std::vector<Edge> new_edges);
    bool has_domi(int u, time_t a, int d);
    bool domi_insert(int u, time_t a, int d);
    void re_add_edges(std::vector<Edge> new_edges);
    void delete_edges(std::vector<Edge> old_edges);
    void re_delete_edges(std::vector<Edge> old_edges);
    std::unordered_set<std::pair<int, time_t>, pair_hash<int, time_t>> red;
    std::tuple<int, time_t, int, time_t, int> find_best(int ou, time_t ot);
    void path(int u, time_t t);
};

void add_test(std::string filename);

void delete_test(std::string filename);

void delete_test2(std::string filename);

void add_test2(std::string filename);